/**
 * @author behrooz mahasseni
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details 
 * @file Temp.java
 * @project bm-vision-java
 * This is a java implementation of distance transforms from http://cs.brown.edu/~pff/dt/. 
 * Calculating the distance transform is done same as the c++ code available in  
 * http://cs.brown.edu/~pff/dt/. But this is a more general implementation which allows 
 * you to use the distance transform beside the images by implementing IDistanceTransformNode 
 * or using DistanceTransformNode. In addition it also includes the 3 dimension extension to 
 * the code
 */

package bm.vision.distancetransform;

public class DistanceTransform {
	public static void distanceTransform(
			IDistanceTransformNode[] distanceTransformNodes) {
		int n = distanceTransformNodes.length;
		double[] d1 = new double[n];
		int[] value = new int[n];
		double[] d2 = new double[n + 1];
		int i = 0;
		value[0] = 0;
		d2[0] = -Float.MAX_VALUE;
		d2[1] = Float.MAX_VALUE;
		for (int q = 1; q <= n - 1; q++) {
			double s = ((distanceTransformNodes[q].getValue() + Math.pow(q, 2)) - (distanceTransformNodes[value[i]]
					.getValue() + Math.pow(value[i], 2)))
					/ (2 * q - 2 * value[i]);
			while (s <= d2[i]) {
				i--;
				s = ((distanceTransformNodes[q].getValue() + Math.pow(q, 2)) - (distanceTransformNodes[value[i]]
						.getValue() + Math.pow(value[i], 2)))
						/ (2 * q - 2 * value[i]);
			}
			i++;
			value[i] = q;
			d2[i] = s;
			d2[i + 1] = Float.MAX_VALUE;
		}

		i = 0;
		for (int q = 0; q <= n - 1; q++) {
			while (d2[i + 1] < q)
				i++;
			d1[q] = Math.pow(q - value[i], 2)
					+ distanceTransformNodes[value[i]].getValue();
		}

		for (int q = 0; q <= n - 1; q++) {
			distanceTransformNodes[q].setValue(d1[q]);
		}
	}

	public static void distanceTransform(
			IDistanceTransformNode[][] distanceTransformNodes) {
		int width = distanceTransformNodes[0].length;
		int height = distanceTransformNodes.length;

		IDistanceTransformNode[] nodes;

		// transform along x
		nodes = new DistanceTransformNode[distanceTransformNodes.length];
		for (int x = 0; x < width; x++) {
			for (int y = 0; y < height; y++) {
				nodes[y] = new DistanceTransformNode(
						distanceTransformNodes[y][x].getValue());
			}
			distanceTransform(nodes);

			for (int y = 0; y < height; y++) {
				distanceTransformNodes[y][x].setValue(nodes[y].getValue());
			}
		}

		// transform along y

		nodes = new DistanceTransformNode[distanceTransformNodes[0].length];
		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				nodes[x] = new DistanceTransformNode(
						distanceTransformNodes[y][x].getValue());
			}
			distanceTransform(nodes);

			for (int x = 0; x < width; x++) {
				distanceTransformNodes[y][x].setValue(nodes[x].getValue());
			}
		}
	}

	public static void distanceTransform(
			IDistanceTransformNode[][][] distanceTransformNodes) {
		int duration = distanceTransformNodes[0][0].length;
		int width = distanceTransformNodes[0].length;
		int height = distanceTransformNodes.length;
		IDistanceTransformNode[] nodes;

		// transform along x
		nodes = new DistanceTransformNode[distanceTransformNodes.length];
		for (int t = 0; t < duration; t++) {
			for (int x = 0; x < width; x++) {
				for (int y = 0; y < height; y++) {
					nodes[y] = new DistanceTransformNode(
							distanceTransformNodes[y][x][t].getValue());
				}
				distanceTransform(nodes);
				for (int y = 0; y < height; y++) {
					distanceTransformNodes[y][x][t].setValue(nodes[y]
							.getValue());
				}
			}
		}

		// transform along y

		nodes = new DistanceTransformNode[distanceTransformNodes[0].length];
		for (int t = 0; t < duration; t++) {
			for (int y = 0; y < height; y++) {
				for (int x = 0; x < width; x++) {
					nodes[x] = new DistanceTransformNode(
							distanceTransformNodes[y][x][t].getValue());
				}
				distanceTransform(nodes);

				for (int x = 0; x < width; x++) {
					distanceTransformNodes[y][x][t].setValue(nodes[x]
							.getValue());
				}
			}
		}
		// transform along time
		nodes = new DistanceTransformNode[distanceTransformNodes[0][0].length];
		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				for (int t = 0; t < duration; t++) {
					nodes[t] = new DistanceTransformNode(
							distanceTransformNodes[y][x][t].getValue());
				}
				distanceTransform(nodes);

				for (int t = 0; t < width; t++) {
					distanceTransformNodes[y][x][t].setValue(nodes[t]
							.getValue());
				}
			}
		}

	}

}
